# -*- coding: utf-8 -*-


class List():

    def __init__(self):
        self.__begin = None
        self.__end = None
        self.__current = None
        self.__size = 0

    def empty(self):
        return self.__size == 0

    def pop(self):
        return self.pop_last()

    def pop_last(self):
        item = None
        if self.__end is not None:
            self.__size -= 1
            item = self.__end[0]
            if self.__end[1] is not None:
                prev = self.__end[1]
                prev[2] = None
                self.__end = prev
            elif self.__begin is None:
                self.__end = None
                self.__begin = None
        return item

    def pop_first(self):
        item = None
        if self.__begin is not None:
            self.__size -= 1
            item = self.__begin[0]
            if self.__begin[2] is not None:
                next = self.__begin[2]
                next[1] = None
                self.__begin = next
            else:
                self.__end = None
                self.__begin = None
        return item

    def add(self, item):
        self.add_last(item)

    def add_first(self, item):
        self.__size += 1
        node = [item, None, None]

        if self.__begin is None:
            self.__begin = node
            self.__end = node
        else:
            node[2] = self.__begin
            node[1] = None
            self.__begin[1] = node
            self.__begin = node

    def add_last(self, item):
        self.__size += 1
        node = [item, None, None]

        if self.__end is None:
            self.__begin = node
            self.__end = node
        else:
            node[1] = self.__end
            node[2] = None
            self.__end[2] = node
            self.__end = node

    def get_first(self):
        return self.__begin

    def get_last(self):
        return self.__end

    def next(self):
        if self.__current is not None:
            self.__current = self.__current[2]
        return self.__current

    def prev(self):
        if self.__current is not None:
            this.__current = self.__current[1]
        return self.__current

    def current(self):
        return self.__current

    def count(self):
        return self.__size

    def reset(self):
        self.__current = self.__begin

    def __iter__(self):
        return ListIterator(self)

    def to_string(self):
        output = ''
        for item in self:
            value = str(item[0])
            if value is None:
                value = ''
            output += value + ';'
        return output

#class ListNode:
#
#    def __init__(self, item):
#        self.item = item
#        self.next = None
#        self.prev = None


class ListIterator:

    def __init__(self, list):
        self.list = list
        self.list.reset()

    def next(self):
        node = self.list.current()
        item = None

        if node is not None:
            item = node[0]
        else:
            raise StopIteration

        self.list.next()

        return item

    def __iter__(self):
        return self
